package algorithmic_data_structure.图.拓扑排序;

import org.junit.Test;

import java.util.*;

public class P207_课程表 {

    class Edge {
        int weight;
        Node from;
        Node to;

        public Edge(int weight,Node from, Node to) {
            this.weight = weight;
            this.from = from;
            this.to = to;
        }
    }
    class Node {
        int value;
        int in;
        int out;
        List<Node> nexts;
        List<Edge> edges;

        public Node(int value) {
            this.value = value;
            in = 0;
            out = 0;
            nexts = new ArrayList<>();
            edges = new ArrayList<>();
        }
    }
    class Graph {
        Map<Integer,Node> nodes;
        Set<Edge> edges;

        public Graph() {
            nodes = new HashMap<>();
            edges = new HashSet<>();
        }
    }
    public Graph generateGraph(int[][] matrix){
        Graph graph = new Graph();
        for (int i = 0; i < matrix.length; i++) {
            int weight = 0;
            int start = matrix[i][1];
            int end = matrix[i][0];
            if (!graph.nodes.containsKey(start)){
                //图中先前还没放入这个节点
                graph.nodes.put(start,new Node(start));//没说节点值是什么，随便取一个先
            }
            if (!graph.nodes.containsKey(end)){
                graph.nodes.put(end,new Node(end));
            }
            Node from = graph.nodes.get(start);
            Node to = graph.nodes.get(end);
            from.nexts.add(to);
            Edge edge = new Edge(weight ,from ,to);
            from.out++;
            to.in++;
            from.edges.add(edge);
            graph.edges.add(edge);
        }
        return graph;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites == null || prerequisites.length == 0){
            return true;
        }
        Graph graph = generateGraph(prerequisites);
        for (int i = 0; i < numCourses; i++) {
            if (!graph.nodes.containsKey(i)){
                graph.nodes.put(i,new Node(i));
            }
        }
        LinkedList<Node> queue = new LinkedList<>();
//        Map<Integer, Node> inMap = new HashMap<>();
        for (Map.Entry<Integer, Node> nodeEntry : graph.nodes.entrySet()) {
            if (nodeEntry.getValue().in == 0){
                queue.add(nodeEntry.getValue());
            }
        }
        int allClasses = 0;
        while (!queue.isEmpty()){
            Node node = queue.poll();
            for (Node next : node.nexts) {
                next.in --;
                if (next.in == 0){
                    queue.offer(next);
                }
            }
            allClasses++;
        }
        if (numCourses == allClasses){
            return true;
        }
        return false;
    }
    @Test
    public void test(){
        System.out.println(canFinish(2, new int[][]{
                {1, 0}
        }));
        System.out.println(canFinish(2, new int[][]{
                {1, 0},{0,1}
        }));
        //5
        //[[1,4],[2,4],[3,1],[3,2]]
        System.out.println(canFinish(5, new int[][]{
                {1, 4},
                {2, 4},
                {3, 1},
                {3, 2},
        }));
    }
}

